package com.practice.suffixtree;


public class SuffixTrie {
	private TrieNode	m_root;
	
	public SuffixTrie(String string) {
		m_root = new TrieNode();
		build(string);
	}
	
	public boolean contains(String word) {
		char[] c = word.toCharArray();
		TrieNode parent = m_root;
		for (int i=0; i<c.length; i++) {
			parent = parent.getChild(c[i]);
			if (parent == null) return false;
		}
		return true;
	}
	
	private void build(String string) {
		char[] c = string.toCharArray();
		for (int i=c.length-1; i>=0; i--) {
			TrieNode parent = m_root;
			for (int j=0; j<c.length-i; j++) {
				parent = parent.addChild(c[i + j]);
			}
		}
	}
	
	private class TrieNode {
		private TrieNode[]				children;
		
		public TrieNode() {
			children = new TrieNode[256];
		}
		
		public TrieNode addChild(char c) {
			if (children[c] == null) children[c] = new TrieNode();
			return children[c];
		}
		
		public TrieNode getChild(char c) {
			return children[c];
		}
	}
}
